import DFS.BipartionDetection;
import DFS.Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Hungarian {
    private Graph graph;
    private int maxMatching = 0;
    private int[] matching;

    public Hungarian(Graph g) {
        BipartionDetection bd = new BipartionDetection(g);
        if (!bd.isBipartite()) {
            throw new IllegalArgumentException("Hungarian only works for bipartion graph.");
        }
        this.graph = g;
        int[] colors = bd.colors();
        matching = new int[g.getVertexNum()];
        Arrays.fill(matching, -1);
        for (int v = 0; v < g.getVertexNum(); v++) {
            if (colors[v] == 0 && matching[v] == -1) {
                if (bfs(v)) {
                    maxMatching++;
                }
            }
        }
    }

    public boolean bfs(int v) {
        Queue<Integer> q = new PriorityQueue<>();
        int[] pre = new int[graph.getVertexNum()];
        Arrays.fill(pre, -1);
        q.add(v);
        pre[v] = v;
        while (!q.isEmpty()) {
            int cur = q.remove();
            for (int next : graph.adj(cur)) {
                if (pre[next] == -1) {
                    if (matching[next] != -1) {
                        pre[next] = cur;
                        pre[matching[next]] = next;
                        q.add(matching[next]);
                    } else {
                        pre[next] = cur;
                        List<Integer> augPath = getAugPath(pre, v, next);
                        for (int i = 0; i < augPath.size(); i += 2) {
                            matching[augPath.get(i)] = augPath.get(i + 1);
                            matching[augPath.get(i + 1)] = augPath.get(i);
                        }
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private List<Integer> getAugPath(int[] pre, int start, int end) {
        List<Integer> res = new ArrayList<>();
        int cur = end;
        while (cur != start) {
            res.add(cur);
            cur = pre[cur];
        }
        res.add(start);
        Collections.reverse(res);
        return res;
    }

    public int maxMatching() {
        return maxMatching;
    }

    public boolean isPerfectMatching() {
        return maxMatching * 2 == graph.getVertexNum();
    }

    public static void main(String[] args) {
        Graph g = new Graph("g.txt");
        Hungarian hungarian = new Hungarian(g);
        System.out.println(hungarian.maxMatching);
    }
}
